package com.company;

import com.company.DivideandConquer.DiffWayToCompute;
import com.company.Dynamic.Frog;
import com.company.Dynamic.KthMagicNumber;
import com.company.Dynamic.LetterCombinations;
import com.company.arrays.ArrayPrinter;
import com.company.arrays.RemoveDuplicates;
import com.company.basic.BinaryNum;
import com.company.basic.GrayCode;
import com.company.basic.SumOfThree;
import com.company.bit.HammingWeight;
import com.company.doubleIndex.LongPressedName;
import com.company.doubleIndex.PalindromeNum;
import com.company.graphic.FindCenterOfGraphic;
import com.company.linkedList.*;
import com.company.matrix.*;
import com.company.modeldesign.*;
import com.company.stack.BackspaceCompare;
import com.company.stack.BaseBallGame;
import com.company.strs.*;
import com.company.tanxin.BoxMinOperation;
import com.company.tanxin.CoveredIntervals;
import com.company.tanxin.MinSetSize;
import com.company.tree.*;
import com.company.unspecific.IntToRoman;
import jdk.swing.interop.SwingInterOpUtils;

import javax.print.DocFlavor;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
//        isBalancedTree();
//        getKthNodeOfList();
//        mergeLinkedList();
//        swapNodes();
//        countBinaryNum();
//        checkIp();
//        hasSameNode();
//        dictionaryTree();
//        rotationList();
//        cashier();
//        lrucache();
//        arrayStack();
//        circularQueue();
//        medianFinder();
//        sortList();
//        baseballGame();
//        backspaceCompare();
//        greyCode();
//        sums();
//        longestSubString();
//            setZero();
//        arrayDump();
//        bulbSwitch();
//        findCopyTargete();
//        expression();
//        treePaths();
//        boxMinOperation();
//        coveredIntervals();
//        miniSetSIZE();
//        longPressedName();
//        hammingWeight();
//            parentheseDepth();
//        balancedStringSplit();
//        flipAndInverImage();
//        getDecimalValue();
//        getArea();
//        basicCalculate();
//        KthSmallest();
//        getLowestAncestor();

//
//        String a = "a";
//        String b = "b";
//        String c = "c";
//        String d = "d";
//
//        String[] nodes = {"a","b","c","d"};
//
//        for (String node : nodes) {
//            int h = node.hashCode()^node.hashCode()>>>16;
//            System.out.println("hash="+Integer.toBinaryString(h));
//            System.out.println("hash^4="+Integer.toBinaryString(h&4));
//        }
//        isPalindromeNum();
//        balanceSearchTree();
//        intToRoman();
//        letterCombination();

//        printNum();
//        findGraphicCenter();
//        kthMagicNumber();
//        minVisitTime();
//        TranslateNum translateNum=new TranslateNum();
//        translateNum.translateNum(12258);
        frog();
    }

    private static void frog(){
        Frog forg=new Frog();
        int[] stones= {0,2};
        forg.canCross(stones);

    }
    private static void minVisitTime(){
        int[][] points={{3,2},{-2,2}};
        VisitAllPoints visitAllPoints=new VisitAllPoints();
        int i = visitAllPoints.minTimeToVisitAllPoints(points);
        System.out.println("totla time = "+i);
    }
    private static void kthMagicNumber(){
        KthMagicNumber kthMagicNumber=new KthMagicNumber();
//        for (int i = 1; i < 10; i=i+4) {
//            System.out.println(kthMagicNumber.getKthMagicNumber(i));
//        }
        System.out.println(kthMagicNumber.getKthMagicNumber(251));
    }

    private static void findGraphicCenter(){
        FindCenterOfGraphic findCenterOfGraphic=new FindCenterOfGraphic();
        int[][] edges = {
                {1,2},
                {2,3},
                {4,2},
        };
        findCenterOfGraphic.findCenter(edges);
    }
    private static void removeNthFromEnd(){
        RemoveNthFromEnd removeNthFromEnd=new RemoveNthFromEnd();
        ListNode node = removeNthFromEnd.removeNthFromEnd(ListNode.buildSampleList(), 5);
        ListNode.printLinkedList(node);
    }

    private static void letterCombination(){
        LetterCombinations letterCombinations=new LetterCombinations();
        letterCombinations.letterCombinations("23");
        letterCombinations.letterCombinations("");
        letterCombinations.letterCombinations("2");
    }

    private static void intToRoman(){
        IntToRoman intToRoman = new IntToRoman();
        for (int i = 0; i < 10; i++) {
            intToRoman.intToRoman(i);
        }
        for (int i = 10; i < 100; i+=10) {
            intToRoman.intToRoman(i);
        }

        for (int i = 100; i < 1000; i+=100) {
            intToRoman.intToRoman(i);
        }

        for (int i = 100; i < 1000; i+=100) {
            intToRoman.intToRoman(i);
        }
    }
    private static void balanceSearchTree(){
        BalanceBinarySearchTree bbst = new BalanceBinarySearchTree();
        bbst.insert(10);
        for (int i = 1; i < 10; i++) {
            bbst.insert(10+i);
            bbst.insert(10-i);

        }
    }

    private static void isPalindromeNum(){
        PalindromeNum palindromeNum=new PalindromeNum();
        int x = 2147483647;

        System.out.println(x+" is palindrome = "+palindromeNum.isPalindrome(x));
    }
    private static void getLowestAncestor(){
        LowestCommonAncestor lowestCommonAncestor=new LowestCommonAncestor();

        TreeNode root = TreeNode.buildSampleTree();




        TreeNode qNode = TreeNode.getNodeByValue(root, 3);
        TreeNode pNode = TreeNode.getNodeByValue(root, 5);

        lowestCommonAncestor.lowestCommonAncestor(root,pNode,qNode);
    }

    private static void KthSmallest(){
        List<Integer> elements = new ArrayList<>();
//        [3,1,4,null,2]
//        1
        elements.add(5);
        elements.add(3);
        elements.add(6);
        elements.add(2);
        elements.add(4);
        elements.add(1);
        TreeNode node = TreeNode.buildSearchTree(elements);


        KthSmallest kthSmallest=new KthSmallest();
        System.out.println(kthSmallest.inTraverse(node));
    }

    private static void basicCalculate(){
        BasicCalculator basicCalculator=new BasicCalculator();

        System.out.println("result = "+basicCalculator.calculate("1+2*3"));
        System.out.println("result = "+basicCalculator.calculate("3/2"));
        System.out.println("result = "+basicCalculator.calculate("1- 1+ 1"));
//        basicCalculator.calculate("1+2");
    }
    private static void getArea(){

        ComputeArea computeArea=new ComputeArea();
        System.out.println(computeArea.computeArea(-2,-2,2,2,3,3,4,4));
    }

    private static void getDecimalValue(){
        DynamicNums dynamicNums=new DynamicNums();
        ListNode h =new ListNode(1);
        ListNode node = h;
        for (int i = 0; i < 4; i++) {
            node.next = new ListNode(0);
            node = node.next;
        }
        ListNode.printLinkedList(h);
        System.out.println(dynamicNums.getDecimalValue(h));
    }

    private static void flipAndInverImage(){
        FlipAndInverImage flipAndInverImage=new FlipAndInverImage();
        int[][] test = {{1,1,0},{1,0,1},{0,0,0}};
//        int[] test1 = {1,1,0,0,0};

        flipAndInverImage.flipImage(test);
        ArrayPrinter.print(test);
        flipAndInverImage.invertImage(test);
        ArrayPrinter.print(test);

    }
    private static void balancedStringSplit(){
        BalancedStringSplit balancedStringSplit=new BalancedStringSplit();
        System.out.println(balancedStringSplit.balancedStringSplit("RLRRLLRLRL"));
        System.out.println(balancedStringSplit.balancedStringSplit("RLLLLRRRLR"));
        System.out.println(balancedStringSplit.balancedStringSplit("LLLLRRRR"));
        System.out.println(balancedStringSplit.balancedStringSplit("RLRRRLLRLL"));
    }
    private static void parentheseDepth(){
        ParenthesesDepth parenthesesDepth=new ParenthesesDepth();
        System.out.println(parenthesesDepth.maxDepth("(1+(2*3)+((8)/4))+1"));
        System.out.println(parenthesesDepth.maxDepth("(1)+((2))+(((3)))"));
        System.out.println(parenthesesDepth.maxDepth("1+(2*3)/(2-1)"));
    }
    private static void hammingWeight(){
        HammingWeight hammingWeight=new HammingWeight();
        for (int i = 0; i < 5; i++) {
            System.out.println(Integer.toBinaryString(i)+"  =  "+hammingWeight.hammingWeight(i));
        }
    }
    private static void  longPressedName(){
        LongPressedName longPressedName=new LongPressedName();
        System.out.println(longPressedName.isLongPressedName("alex","aaleex"));

    }


    private static void miniSetSIZE(){
        MinSetSize minSetSize=new MinSetSize();
//        int[] arr = {3,3,3,3,5,5,5,2,2,7};
//        int[] arr = {1,9};
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        System.out.println(minSetSize.minSetSize(arr));
    }
    private static void coveredIntervals(){
        CoveredIntervals coveredIntervals=new CoveredIntervals();
        int[][] test={{34335,39239},{15875,91969},{29673,66453},{53548,69161},{40618,93111}};
        System.out.println(coveredIntervals.removeCoveredIntervals(test));
    }
    private static void boxMinOperation(){
        BoxMinOperation boxMinOperation=new BoxMinOperation();
        ArrayPrinter.print(boxMinOperation.minOperations("110"));
        ArrayPrinter.print(boxMinOperation.minOperations("001011"));
    }

    private static void treePaths(){
        TreePath treePath=new TreePath();
        System.out.println(treePath.binaryTreePaths(TreeNode.buildSampleTree()));
        System.out.println(treePath.binaryTreePaths(TreeNode.buildLineTree()));


    }

    private static void expression(){
//        DiffWayToCompute diffWayToCompute=new DiffWayToCompute();
//        diffWayToCompute.diffWaysToCompute("2-1-1");

        DiffWayToCompute.Operate operate = DiffWayToCompute.Operate.fromExpress("(1+2)");
        System.out.println(operate.toString());
        System.out.println(operate.getResult());

    }

    private static void findCopyTargete(){
        TargetCopy targetCopy=new TargetCopy();
        TreeNode originTree = TreeNode.buildSampleTree();
        TreeNode copyTree = TreeNode.buildSampleTree();
        TreeNode target = TreeNode.getNodeByValue(originTree, 4);
        targetCopy.getTargetCopy(originTree,copyTree,target);
    }
    private static void bulbSwitch(){
        BulbSwitch bulbSwitch=new BulbSwitch();
        for (int i = 0; i < 3; i++) {
            int i1 = bulbSwitch.bulbSwitch(i+1);
            System.out.println(i1);
//            ArrayPrinter.print(i1);
        }
    }
    private static void arrayDump(){
        RemoveDuplicates removeDuplicates = new RemoveDuplicates();
        int[] nums= {0,0,1,1,1,1,2,3,3};
        int i = removeDuplicates.removeDuplicates(nums);
        System.out.println(i);
    }

    private static void setZero(){
        SetZeros setZeros = new SetZeros();
        int[][] matrix = {{1,1,1},{1,0,1},{1,1,1}};
        MatrixPrinter.print(matrix);
        setZeros.setZeroes(matrix);
        MatrixPrinter.print(matrix);
    }
    private static void longestSubString(){
        LongestSubStr longestSubStr=new LongestSubStr();
        System.out.println(longestSubStr.lengthOfLongestSubstring("ac"));
        System.out.println(longestSubStr.lengthOfLongestSubstring("acacbb"));
        System.out.println(longestSubStr.lengthOfLongestSubstring("abcabcbb"));
    }

    private static void sums() {
        SumOfThree sumOfThree = new SumOfThree();

        int[] nums = {-1,0, 1, 2, -1,-4};

        Arrays.sort(nums);
        List<List<Integer>> lists = sumOfThree.threeSum(nums);
//        List<List<Integer>> lists = sumOfThree.twoSum(nums,0);
        System.out.println(lists);
    }

    private static void greyCode() {
        GrayCode code = new GrayCode();
        GrayCode.printList(code.grayCode(2));
        GrayCode.printList(code.grayCode(3));

    }

    private static void backspaceCompare() {
        BackspaceCompare backspaceCompare = new BackspaceCompare();
        boolean b = backspaceCompare.backspaceCompare("abcd", "dbcd");
        System.out.println(b);
    }

    private static void baseballGame() {
        BaseBallGame baseBallGame = new BaseBallGame();
        String[] opts = {"5", "2", "C", "D", "+"};
        String[] opts2 = {"5", "-2", "4", "C", "D", "9", "+", "+"};
        System.out.println("score = " + baseBallGame.calPoints(opts));
        System.out.println("score = " + baseBallGame.calPoints(opts2));
    }


    private static void sortList() {
        SortList sortList = new SortList();
        ListNode node = sortList.sortList(ListNode.buildSampleList(2));
        ListNode.printLinkedList(node);
    }

    private static void medianFinder() {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(3);
        System.out.println(medianFinder.findMedian());
    }

    private static void circularQueue() {
        MyCircularQueue circularQueue = new MyCircularQueue(3);
        System.out.println(circularQueue.enQueue(2));
        System.out.println(circularQueue.Rear());
        System.out.println(circularQueue.Front());
        System.out.println(circularQueue.deQueue());
        System.out.println(circularQueue.Front());
        System.out.println(circularQueue.deQueue());
        System.out.println(circularQueue.Front());
        System.out.println(circularQueue.enQueue(4));
        System.out.println(circularQueue.enQueue(2));
        System.out.println(circularQueue.enQueue(2));
        System.out.println(circularQueue.enQueue(3));

    }

    private static void arrayStack() {
        TripleInOne tripleInOne = new TripleInOne(5);
        System.out.println(tripleInOne.isEmpty(0));
        System.out.println(tripleInOne.isEmpty(1));
        System.out.println(tripleInOne.isEmpty(2));
        for (int i = 0; i < 3; i++) {
            tripleInOne.push(0, i);
            tripleInOne.push(1, i);
            tripleInOne.push(2, i);
        }
        System.out.println(tripleInOne.isEmpty(0));
        System.out.println(tripleInOne.isEmpty(1));
        System.out.println(tripleInOne.isEmpty(2));
        for (int i = 0; i < 3; i++) {
            System.out.println(tripleInOne.pop(0));
            System.out.println(tripleInOne.pop(1));
            System.out.println(tripleInOne.pop(2));
        }
    }

    private static void lrucache() {
        LRUCache lruCache = new LRUCache(2);
        System.out.println(lruCache.get(2));
        lruCache.put(2, 6);
        System.out.println(lruCache.get(1));
        lruCache.put(1, 5);
        lruCache.put(1, 2);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(2));
    }


    private static void cashier() {
/*["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],
[[1,2],[1,2]],[[3,7],[10,10]],
[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],
[[4],[10]],
[[7,3],[10,10]],
[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],
[[2,3,5],[5,3,2]]
]*/
        int[] products = {1, 2, 3, 4, 5, 6, 7};
        int[] prices = {100, 200, 300, 400, 300, 200, 100};

        int[][] custmor = {
                {},
                {},
                {},
                {}
        };

        Cashier cashier = new Cashier(3, 50, products, prices);
        int[] myp = {1};
        int[] mAmount = {1};

        for (int i = 0; i < 10; i++) {
            double bill1 = cashier.getBill(myp, mAmount);
            System.out.println("total bill " + bill1);
        }
    }

    private static void rotationList() {
        RotationList rotationList = new RotationList();

        ListNode node = rotationList.rotateRight(ListNode.buildSampleList(1), 0);
        ListNode.printLinkedList(node);

    }


    private static void dictionaryTree() {
        DictionaryOfWord dictionaryOfWord = new DictionaryOfWord();
        dictionaryOfWord.insertNewWord("a");
        dictionaryOfWord.insertNewWord("app");
        dictionaryOfWord.insertNewWord("application");

        System.out.println("has word a " + dictionaryOfWord.hasWord("a"));
        System.out.println("has word app " + dictionaryOfWord.hasWord("app"));
        System.out.println("has word apple " + dictionaryOfWord.hasWord("apple"));
    }

    private static void hasSameNode() {
        FindNode findNode = new FindNode();

        ListNode h = ListNode.buildSampleList();
        ListNode node = ListNode.buildSampleList();
        System.out.println(findNode.hasSameNode(h, h));
        System.out.println(findNode.hasSameNode(h, node));
    }

    private static void checkIp() {
        IPChecker ipChecker = new IPChecker();
        System.out.println(ipChecker.checkIp("1.1.1.1"));
        System.out.println(ipChecker.checkIp("1.1.1."));
        System.out.println(ipChecker.checkIp("1.1.1.a"));
    }

    private static void countBinaryNum() {
        BinaryNum binaryNum = new BinaryNum();
        System.out.println("1 的个数 ： " + binaryNum.countOne(7));

    }

    private static void swapNodes() {
        SwapNodes swapNodes = new SwapNodes();
        ListNode node = swapNodes.swapPairs(new ListNode(1));
        ListNode.printLinkedList(node);
    }

    private static void mergeLinkedList() {
        MergeOrderedList mergeList = new MergeOrderedList();
        ListNode s = new ListNode(2);
        ListNode i = new ListNode(1);
        ListNode node = mergeList.mergeTwoLists(s, i);
        ListNode.printLinkedList(node);

    }

    private static void getKthNodeOfList() {
        KthNodeOfList kthNodeOfList = new KthNodeOfList();
        for (int k = 1; k < 4; k++) {
            ListNode kthFromEnd = kthNodeOfList.getKthFromEnd(ListNode.buildSampleList(), k);
            System.out.println("k = " + k + "result = " + kthFromEnd.val);
        }

    }

    private static void isBalancedTree() {
        TreeNode root = TreeNode.buildSampleTree();
        TreeNode lineTree = TreeNode.buildLineTree();
        BalancedTree balancedTree = new BalancedTree();
        boolean balancedTree1 = balancedTree.isBalancedTree(root);
        System.out.println(balancedTree1);

        boolean b = balancedTree.isBalancedTree(lineTree);
        System.out.println(b);

    }

    private static void deepOfTree() {
        DeepOfTree deepOfTree = new DeepOfTree();
        TreeNode tree = TreeNode.buildLineTree();
        int d = deepOfTree.getDeepOfTree(tree);
        System.out.printf("" + d);
    }

    private static void traverseTree() {
        TraverseTree traverseTree = new TraverseTree();
        TreeNode treeRoot = TreeNode.buildSampleTree();
        traverseTree.levelZTraverse(treeRoot);
    }

    private static void revertLinkedList() {
        // 翻转链表
        RevertLinkedList revertLinkedList = new RevertLinkedList();
        ListNode source = RevertLinkedList.buildSampleList();
        ListNode.printLinkedList(source);
        ListNode result = revertLinkedList.solution(source);
        ListNode.printLinkedList(result);
    }
}
